#include <vector>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

class Solution {
public:
    string alienOrder(vector<string>& words) {
        // 入度表，26个英文字母
        int indegree[26];
        memset(indegree, -1, sizeof(indegree));
        
        // 初始化出现过的字符的入度为0
        for (string& w : words) {
            for (char c : w) {
                indegree[c - 'a'] = 0;
            }
        }
        
        // 构建邻接表
        vector<vector<int>> graph(26);
        
        // 遍历单词对，建立字符间的先后关系
        for (int i = 0; i < words.size() - 1; i++) {
            string& cur = words[i];
            string& next = words[i + 1];
            int len = min(cur.length(), next.length());
            int j = 0;
            for (; j < len; j++) {
                if (cur[j] != next[j]) {
                    // 建立从cur[j]到next[j]的边
                    graph[cur[j] - 'a'].push_back(next[j] - 'a');
                    indegree[next[j] - 'a']++;
                    break;
                }
            }
            // 如果前一个单词更长且是后一个单词的前缀，则排序无效
            if (j < cur.length() && j == next.length()) {
                return "";
            }
        }
        
        // 统计出现的字符种类数
        int kinds = 0;
        queue<int> q;
        for (int i = 0; i < 26; i++) {
            if (indegree[i] != -1) {
                kinds++;
            }
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        // 拓扑排序
        string ans;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            ans += (char)(cur + 'a');
            
            for (int next : graph[cur]) {
                if (--indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        // 检查是否所有字符都被包含
        return ans.length() == kinds ? ans : "";
    }
};
